import java.util.*;

/**
 * 面试题 08.02. 迷路的机器人
 * https://leetcode-cn.com/problems/robot-in-a-grid-lcci/
 */
public class Solutions_mianshi_08_02 {
    public static void main(String[] args) {
//        int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        // output: {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}}

        int[][] obstacleGrid = {{0, 0}};
        // output: {{0, 0}, {0, 1}}

        List<List<Integer>> result = pathWithObstacles(obstacleGrid);
        System.out.println(result);
    }

    private static int row = 0;
    private static int col = 0;

    public static List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        List<List<Integer>> res = new ArrayList<>();
        row = obstacleGrid.length;
        if (row < 1) {
            return res;
        }
        col = obstacleGrid[0].length;
        if (col < 1) {
            return res;
        }
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            // 起点或终点是障碍物时
            return res;
        }
        // 标记某坐标是否访问过，若访问过，还能够再次访问到，说明从该坐标不能到达终点
        // 比如，从 [0, 1] 向下移动和 [1, 0] 向右移动都能到 [1, 1]，若从 [0, 1] 向下进入 [1, 1] 时，
        // 将 [1, 1] 标记为已访问了，如果 [1, 1] 能够到达终点，也就不会遍历到 [1, 0] 了，所以遍历 [1, 0] 时
        // 不考虑向右移到 [1, 1]
        boolean[][] visited = new boolean[row][col];
        dfs(res, obstacleGrid, 0, 0, visited);
        return res;
    }

    // [i, j] 行坐标为 i，列坐标为 j
    public static boolean dfs(List<List<Integer>> res, int[][] obstacleGrid,
                              int i, int j, boolean[][] visited) {
        // 已到过的坐标，不能够到达终点时，标记为 true
        visited[i][j] = true;
        res.add(Arrays.asList(i, j));
        if (i == row - 1 && j == col - 1) {
            // 结束条件：到达终点
            return true;
        }
        // 向右移动
        // 行坐标不变，列坐标加 1
        // 判断是否可以向右移动：1.索引未越界，2.右侧坐标不是障碍物，3.右侧坐标未访问过
        if (j < col - 1 && obstacleGrid[i][j + 1] != 1 && visited[i][j + 1] != true) {
            boolean rightRes = dfs(res, obstacleGrid, i, j + 1, visited);
            if (rightRes) {
                return true;
            }
        }
        // 向下移动
        // 行坐标加 1，列坐标不变
        // 判断是否可以向下移动：1.索引未越界，2.下边坐标不是障碍物，3.下边坐标未访问过
        if (i < row - 1 && obstacleGrid[i + 1][j] != 1 && visited[i + 1][j] != true) {
            boolean downRes = dfs(res, obstacleGrid, i + 1, j, visited);
            if (downRes) {
                return true;
            }
        }
        // 移除当前选择，即从该坐标，向右或向下，都不能到达终点
        res.remove(res.size() - 1);
        // 返回 false，说明从该坐标不能够到达终点
        return false;
    }
}
